


#ifndef _LIST_H_
#define _LIST_H_


#include "stl_type.h"


/// <summary>
/// 返回剩余可分配节点数量
/// </summary>
/// <returns></returns>
int ListNode_remain(void);

/// <summary>
/// 单向链表，只能向后索引。 void*
/// </summary>
typedef struct ListNode__
{
	Datapointer datap;
	struct ListNode__* next;
}ListNode;

/// <summary>
/// 单向循环链表结构体。只记录尾节点，使用尾节点可以方便尾部插入数据，
/// 尾节点的下一个节点是头节点。
/// 如果是按序插入，就是从小往大排列，头节点是最小的节点。
/// </summary>
typedef struct  __List__
{
	/// 链表节点数量。
	int count; 
	/// 链表的比较函数。key1 > key2返回1，key1 < key2返回-1,key1 = key2返回0.
	int (*match)(Datapointer key1, Datapointer key2);	
	//CompareFuncPoint match;
	/// 尾节点
	ListNode* tail;  
}List;




/// <summary>
/// 初始化链表
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="c">链表节点的比较函数。在有序插入的时候要用到。这里的 Datapointer 是 ListNode* </param>
void list_init(List* list, int (*c)(Datapointer, Datapointer));

/// <summary>
/// 销毁链表。
/// </summary>
/// <param name="list">链表结构体</param>
void list_destroy(List* list);

/// <summary>
/// 链表头节点的数据
/// </summary>
/// <param name="list">链表</param>
/// <returns>数据指针 </returns>
Datapointer list_head(List* list);

/// <summary>
/// 链表尾节点的数据
/// </summary>
/// <param name="list">链表</param>
/// <returns>数据指针 </returns>
Datapointer list_tail(List* list);

/// <summary>
/// 在链表尾部插入一个元素。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="datap">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool list_push_back(List* list, Datapointer datap);

/// <summary>
/// 在链表头部插入一个元素。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="datap">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool list_push_front(List* list, Datapointer datap);

/// <summary>
/// 在链表头部弹出一个数据
/// </summary>
/// <param name="list">链表结构体</param>
/// <returns>是否操作成功</returns>
Datapointer list_pop_front(List* list);

/// <summary>
/// 按序插入节点。按照从小到大的顺序插入。如果所有元素都是按序插入的，整个链表就是有序的。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="datap">新插入的节点</param>
bool list_ins_orderly(List* list, Datapointer datap);


/// <summary>
/// 在 node 后面插入一个新元素
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="node">定位的节点</param>
/// <param name="datap">新插入的节点</param>
/// <returns>是否插入成功，如果node是合法的节点，是可以成功插入的</returns>
bool list_ins_next(List* list, ListNode* node, Datapointer datap);

/// <summary>
/// 在 node 前面插入一个新元素.
/// 等效于在node后面插一个元素，然后调换node和node->next 的值
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="node">定位的节点</param>
/// <param name="datap">新插入的节点的数据</param>
/// <returns>是否插入成功，如果node是合法的节点，是可以成功插入的</returns>
bool list_ins_prev(List* list, ListNode* node, Datapointer datap);

/// <summary>
/// 在链表 中移除 node 元素，为了使操作时间复杂度在O(1),采用下面的方法：
/// 将node下一个节点的值赋值给node，再删除下一个节点。
/// 注意：这里有个风险：如果node是尾节点，那么删除之后，原来的头节点会变成尾节点。
/// 不过，链表的大部分用途不关心节点顺序。如果需要关心节点顺序，就用list_remove_next
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="node">移除的节点</param>
/// <returns>是否操作成功。如果node是合法的节点，是可以操作成功的</returns>
bool list_remove(List* list, ListNode* node);

/// <summary>
/// 在链表 中移除 node 下一个节点。
/// 如果下一个节点是尾节点，node会成为新的尾节点。
/// 如果node是尾节点，会移除头节点。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="node">移除的节点</param>
/// <returns>是否操作成功。如果node是合法的节点，是可以操作成功的</returns>
bool list_remove_next(List* list, ListNode* node);


// 测试list
void test_list(void);







#endif

//

